application note MPT1327 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. error detection & correction of MPT1327 formatted messages error detection & correction of MPT1327 formatted messages using mx429a or mx809 devices 1.1 background MPT1327 messages are transmitted as 64-bit codewords, where each codeword contains 48 information bits followed by 16 check bits: bit no: 1 48 49 64 information field check bits (bit number 1 is transmitted first.) these check bits allow the receive terminal to detect all odd numbers of errors, any 2 or 4 errors, and any error-burst up to length 16 in a codeword, and also to correct errors in the received codeword, although it should be noted that the higher the degree of error correction applied, the more likely is false decoding. this document gives algorithms for: generation of the check bits of a transmitted codeword. received codeword error detection. limited error correction of a received codeword. these algorithms may be used with any bit or byte oriented modem, such as the mx429a or mx809, although the mx429a and mx809 devices can perform check bit generation and error detection automatically and the mx429a also provides a 16-bit syndrome output which may be used to aid error correction. 1.2 generation of transmit codeword check bits 1.2.1 theory the first 15 check bits are derived from a (63,48) cyclic code by using codeword bits 1 to 48 as the coefficients x62 to x15 (in that order) of a 63 bit polynomial, which is then divided modulo-2 by the generating polynomial; x15 + x14 + x13 + x11 + x4 + x2 + x0 (11101000 00010101 binary) on completion of the division, the 15 coefficients x14 to x0 of the remainder are used as the first 15 check bits (codeword bits 49 to 63), with the x0 coefficient (bit 63 of the complete codeword) inverted. finally, bit 64 of the codeword is added to provide an even parity check of the whole 64-bit codeword.
error detection & correction of MPT1327 formatted messages 2 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 1.2.2 example of transmit codeword generation information field; 6 data bytes 89 ab cd ef 12 34 hex 10001001 10101011 11001101 11101111 00010010 00110100 binary polynomial division x 62 ..x 0 10001001 10101011 11001101 11101111 00010010 00110100 00000000 0000000 11101000 00010101 1100001 10111110 1 1110100 00001010 1 10101 10110100 010 11101 00000010 101 1000 10110110 1110 1110 10000001 0101 110 00110111 10111 111 01000000 10101 1 01110111 0001010 1 11010000 0010101 10100111 00111111 11101000 00010101 1001111 00101010 1 1110100 00001010 1 111011 00100000 01 111010 00000101 01 1 00100101 0010111 1 11010000 0010101 11110101 00000101 11101000 00010101 11101 00010000 000 11101 00000010 101 10010 10110010 001 11101 00000010 101 1111 10110000 1001 1110 10000001 0101 1 00110001 1100010 1 11010000 0010101 11100001 11101110 11101000 00010101 1001 11111011 0000 1110 10000001 0101 111 01111010 01010 111 01000000 10101 111010 11111000 00 111010 00000101 01 11111101 0100000 remainder with last bit inverted: 11111101 0100001 complete codeword, including parity bit: bit; 1 64 10001001 10101011 11001101 11101111 00010010 00110100 11111101 01000010 89 ab cd ef 12 34 fd 42
error detection & correction of MPT1327 formatted messages 3 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 1.2.3 c language algorithm /**********************************************************************************/ /* function gen_ckbits() returns the first 15 check bits of a transmit */ /* codeword (codeword bits 49 to 63). bit 15 of the returned value will */ /* be codeword bit 49, bit 1 of the returned value will be codeword bit */ /* 63, and the lsb (bit 0) should be ignored. */ /* the last bit (64) of the codeword must be derived separately, to */ /* give even parity of the whole 64-bit codeword. */ gen_ckbits() { int n,bit; unsigned int ckbits = 0; /* clear check bits */ for(n=1;n <= 48;n++) /* 48 information bits */ { /* */ bit = getbit_tx(n); /* get each bit in turn */ if( 1 & (bit ^ (ckbits >> 15))) /* xor tx bit with msb */ /* of checkbits and if */ /* the result == 1 */ ckbits ^= 0x6815; /* then xor checkbits */ /* with 6815 hex */ ckbits <<= 1; /* ... shift check bit word */ /* one bit left, */ } return(ckbits ^ 0x0002); /* return checkbits with */ /* codeword bit 63 inverted */ } /* function getbit_tx(n) should return bit n (1 to 48) of the transmit*/ /* codeword information field. */ getbit_tx(n) { return(/* 1 or 0 */); }
error detection & correction of MPT1327 formatted messages 4 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 1.3 receive codeword checking & error correction 1.3.1 theory the parity of the received 64-bit codeword is checked, then bit 63 of the codeword is inverted. the first 63 bits of the resulting codeword are then used as the coefficients x77 to x15 of a 77 bit polynomial, which is then divided modulo-2 by the generating polynomial. if the remainder is zero, and the parity check is met, then no errors have been detected. the 15-bit remainder of this division is used as the least significant 15 bits of the 16-bit syndrome word generated by the mx429 (and by the algorithm of section 3.4), while the msb of the syndrome word is set to 1 if the parity of the received codeword is incorrect. the resulting syndrome word value can give an indication of which bit(s) of the codeword have been received incorrectly; see section 3.4. 1.3.2 example of receive codeword checking: no errors received codeword: 6 bytes: 89 ab cd ef 12 34 fd 42 10001001 10101011 11001101 11101111 00010010 00110100 11111101 01000010 bit; 164 step 1: even parity checked ok step 2: invert bit 63 then divide first 63 bits (shifted left 15 places) by generating polynomial: x 77 ...x 0 10001001 10101011 11001101 11101111 00010010 00110100 11111101 01000000 00000000 000000 11101000 00010101 1100001 10111110 1 1110100 00001010 1 10101 10110100 010 11101 00000010 101 1000 10110110 1110 1110 10000001 0101 110 00110111 10111 111 01000000 10101 1 01110111 0001010 1 11010000 0010101 10100111 00111111 11101000 00010101 1001111 00101010 1 1110100 00001010 1 111011 00100000 01 111010 00000101 01 1 00100101 0010111 1 11010000 0010101 11110101 00000101 11101000 00010101 11101 00010000 000 11101 00000010 101 10010 10110010 001 11101 00000010 101 1111 10110000 1001 1110 10000001 0101 1 00110001 1100010 1 11010000 0010101 11100001 11101110 11101000 00010101 1001 11111011 1111 1110 10000001 0101 111 01111010 10101 111 01000000 10101 111010 00000101 01 111010 00000101 01 000000 00000000 00000000 00000000 0000 00 remainder = zero mx429 syndrome word: 00000000 00000000 no errors detected
error detection & correction of MPT1327 formatted messages 5 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 1.3.3 example of receive codeword checking: 2 errors received codeword: 6 bytes: bits 9 & 10 in error 89 6b cd ef 12 34 fd 42 10001001 01101011 11001101 11101111 00010010 00110100 11111101 01000010 errors; xx bit; 1 64 step 1: even parity checked ok step 2: invert bit 63 then divide first 63 bits (shifted left 15 places) by generating polynomial: x 77 .................................................................... ........x 0 10001001 01101011 11001101 11101111 00010010 00110100 11111101 01000000 00000000 000000 11101000 00010101 1100001 01111110 1 1110100 00001010 1 10101 01110100 010 11101 00000010 101 1000 01110110 1110 1110 10000001 0101 110 11110111 10111 111 01000000 10101 1 10110111 0001010 1 11010000 0010101 1100111 00111111 1 1110100 00001010 1 10011 00110101 011 11101 00000010 101 1110 00110111 1100 1110 10000001 0101 10110110 10011111 11101000 00010101 1011110 10001010 0 1110100 00001010 1 101010 10000000 10 111010 00000101 01 10000 10000101 110 11101 00000010 101 1101 10000111 0111 1110 10000001 0101 11 00000110 001000 11 10100000 010101 10100110 01110110 11101000 00010101 1001110 01100011 0 1110100 00001010 1 111010 01101001 10 111010 00000101 01 1101100 11110100 1 1110100 00001010 1 11000 11111110 011 11101 00000010 101 101 11111100 11011 111 01000000 10101 10 10111100 011101 11 10100000 010101 1 00011100 0010000 1 11010000 0010101 11001100 00001011 11101000 00010101 100100 00011110 01 111010 00000101 01 11110 00011011 000 11101 00000010 101 11 00011001 101000 11 10100000 010101
error detection & correction of MPT1327 formatted messages 6 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 10111001 11110100 11101000 00010101 1010001 11100001 0 1110100 00001010 1 100101 11101011 10 111010 00000101 01 11111 11101110 110 11101 00000010 101 10 11101100 0 11000 11 10100000 0 10101 1 01001100 0011010 1 11010000 0010101 10011100 00011110 11101000 00010101 111010 0 00001011 0 111010 0 00001010 1 remainder; non zero 1 100000 mx429 syndrome word: 00000000 01100000 therefore, from the table in section 3.4, codeword bits 9 & 10 of the received codeword are incorrect. 1.3.4 c language algorithm the following algorithm produces a 16-bit syndrome similar to that generated by the mx429, which will have a value of zero only if no errors have been detected in the received codeword. /*****************************************************************************************/ /* function calc_syndrome() returns the 16-bit syndrome of a received */ /* MPT1327 64-bit codeword. */ calc_syndrome() { int n,bit; int parity=0; /* clear parity register */ int syndrome=0; /* clear 16-bit syndrome */ for(n = 1;n <= 64;n++) /* 64-bit codeword... */ { /* */ bit = getbit_rx(n); /* get each bit in turn;.. */ parity ^= bit; /* .. update parity */ if(n == 63) bit ^= 1; /* .. then invert bit 63 */ if(n < 64) /* .. for bits 1 to 63;.... */ { /* .. shift parity word */ syndrome <<= 1; /* one bit left. */ if( 1 & (bit ^ (syndrome >> 15))) /* .. xor rx bit with */ /* msb of parity word, */ /* and if result == 1 */ syndrome ^= 0x6815; /* then xor syndrome */ /* with 6815 hex. */ } /* */ } syndrome &= 0x7fff; /* finally, replace msb of */ if(parity) /* syndrome word with the */ syndrome |= 0x8000; /* calculated parity bit */ return(syndrome); } /* function getbit_rx(n) should return the bit n of the received */ /* codeword; bit 1 is the first bit to be received, bit 64 the last. */ getbit_rx(n) { return(/* 1 or 0 */); }
error detection & correction of MPT1327 formatted messages 7 application note 1998 mx com, inc. www. mxcom.com tel: 800 638 5577 336 744 5050 fax: 336 744 5054 doc. # 20830066.002 4800 bethania station road, winston-salem, nc 27105-1201 usa. all trademarks and service marks are held by their respective c ompanies. 1.4 error correction single-bit and bit-pair errors in a received codeword may be corrected by comparing the syndrome word (generated by the mx429 or the algorithm of section 3.4) against the entries in the following table, and if a match is found inverting the corresponding bits. syndrome (hex) error bits syndrome (hex) error bits syndrome (hex) error bits syndrome (hex) error bits 0003 0006 000c 0018 0030 0060 00c0 0180 0300 0600 0c00 15d3 1763 1800 18cd 193b 1e1b 21cd 220b 2867 2ba6 2d31 2e7d 2ec6 3000 3149 319a 3276 3657 3c36 439a 4416 14, 15 13, 14 12, 13 11, 12 10, 11 9, 10 8, 9 7, 8 6, 7 5, 6 4, 5 43, 44 20, 21 3, 4 28, 29 59, 60 31, 32 56, 57 38, 39 35, 36 42, 43 49, 50 25, 26 19, 20 2, 3 51, 52 27, 28 58, 59 53, 54 30, 31 55, 56 37, 38 468d 4841 4989 4b7b 4bd7 4e0f 502a 50ce 51b7 51e1 530d 574c 5a62 5cd1 5cfa 5d8c 6000 6039 6292 6334 64ec 650f 6815 6cae 6f21 740b 786c 7897 7b07 7ee3 7fbb 8000 40, 41 61, 62 33, 34 45, 46 22, 23 16, 17 62, 63 34, 35 46, 47 23, 24 17, 18 41, 42 48, 49 47, 48 24, 25 18, 19 1, 2 36, 37 50, 51 26, 27 57, 58 39, 40 63, 64 52, 53 54, 55 15, 16 29, 30 60, 61 32, 33 44, 45 21, 22 64 8001 8002 8004 8008 8010 8020 8040 8080 8100 8200 8400 8800 88e9 8a09 8cb1 8d21 9000 90c7 91d2 9412 9962 9a2b 9a42 a000 a017 a18e a305 a3a4 a51f a824 b2c4 b44f 15 14 13 12 11 10 9 8 7 6 5 4 60 32 44 21 3 52 59 31 43 26 20 2 37 51 40 58 55 30 42 48 b456 b484 b83f b887 b929 b94d ba05 c000 c02e c31c c60a c748 c885 ca3e d048 e401 e588 e685 e815 e849 e89e e8ac e908 ee2d f07e f10e f252 f29a f40a f91f fc69 25 19 62 34 46 23 7 1 36 50 39 57 28 54 29 38 41 56 63 35 47 24 18 49 61 33 45 22 16 27 53 example: transmitted codeword: bit; 1 64 10001001 10101011 11001101 11101111 00010010 00110100 11111101 01000010 errors; xx received codeword: 10001001 01101011 11001101 11101111 00010010 00110100 11111101 01000010 for this received codeword, the syndrome will be 0060h, which appears in the table, indicating that the 9th & 10th bits received are incorrect and should be inverted.
|
